/**
 * 最小生成树 Prim 算法
*/

#include "MGraph.c"

#ifndef MGRAPH_PRIM
#define MGRAPH_PRIM

/* 邻接矩阵存储 - Prim最小生成树算法 */
/* 返回未被收录顶点中dist最小者 */
int findMinDist(MGraph *graph, WeightType dist[] ) { 
    int minV = -1; // 默认顶点不存在，-1作为标记
    WeightType minDist = MaxWeight;

    for (int v=0; v < graph->vertexNum; v++) {
        if (dist[v] != 0 && dist[v] < minDist) {
            /* 若V未被收录，且dist[V]更小 */
            minDist = dist[v]; /* 更新最小距离 */
            minV = v; /* 更新对应顶点 */
        }
    }
    return minV;
}

/* 将最小生成树保存为邻接表存储的图MST，返回最小权重和 */
WeightType prim(MGraph *graph, MGraph *MST) { 
    // dist[v] == 0, 表示 v 已收录
    WeightType *dist = (WeightType*) calloc(graph->vertexNum, sizeof(WeightType));
    int *parent = (int*) calloc(graph->vertexNum, sizeof(int));
    /* 初始化。默认初始点下标是0 */
    for (int v=0; v < graph->vertexNum; v++) {
        /* 这里假设若V到W没有直接的边，则Graph->G[v][w]定义为MaxWeight */
        dist[v] = graph->g[0][v];
        parent[v] = 0; /* 暂且定义所有顶点的父结点都是初始点0 */ 
    }
    WeightType totalWeight = 0; /* 初始化权重和     */
    
    /* 将初始点0收录进MST */
    dist[0] = 0;
    int vCount = 1;     /* 初始化收录的顶点数 */
    parent[0] = -1;     /* 当前树根是0 */
    // printf("收录 %d, parent[%d]=%d\n", 0, 0, parent[0]);
    while (1) {
        int v = findMinDist(graph, dist);
        // printf("未被收录顶点中dist最小者: v=%d\n", v);
        /* V = 未被收录顶点中dist最小者 */
        if (v == -1) /* 若这样的V不存在 */
            break;   /* 算法结束 */
            
        /* 将V及相应的边<parent[V], V>收录进MST */
        int v1 = parent[v];
        int v2 = v;
        WeightType weight = dist[v];
        insertEdge(MST, v1, v2, weight);
        totalWeight += dist[v];
        dist[v] = 0;
        vCount++;
        
        for(int w=0; w < graph->vertexNum; w++) {
            /* 对图中的每个顶点W */
            if (dist[w]!=0 && graph->g[v][w] < MaxWeight) {
                /* 若W是V的邻接点并且未被收录 */
                if (graph->g[v][w] < dist[w]) {
                    /* 若收录V使得dist[w]变小 */
                    dist[w] = graph->g[v][w]; /* 更新dist[w] */
                    parent[w] = v; /* 更新树 */
                }
            }
        }
    } /* while结束*/
    if (vCount < graph->vertexNum) {
        /* MST中收的顶点不到|V|个 */
       totalWeight = -1;
    }
    free(dist);
    free(parent);
    return totalWeight;   /* 算法执行完毕，返回最小权重和或错误标记 */ 
}

#endif
